package com.gxc.string;

import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

/**
 * * 字符串重排
 * *
 * * 题目描述
 * * 给定一个只包含大写英文字母的字符串S，要求你给出对S重新排列的所有不相同的排列数。
 * * 如：S为ABA，则不同的排列有ABA、AAB、BAA三种。
 * *
 * * 解答要求
 * * 输入
 * * 输入一个长度不超过10的字符串S，我们确保都是大写的。
 * *
 * * 输出
 * * 输出S重新排列的所有不相同的排列数（包含自己本身）。
 * *
 * * 样例
 * * 输入样例 1
 * * ABA
 * * 输出样例 1
 * * ABA、AAB、BAA
 */
public class StringPermutationGenerator {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine().trim();
        scanner.close();

        Set<String> permutations = generatePermutations(input);
        permutations.forEach(System.out::println);
    }

    private static Set<String> generatePermutations(String input) {
        Set<String> result = new TreeSet<>();
        permute(input.toCharArray(), 0, result);
        return result;
    }

    private static void permute(char[] arr, int start, Set<String> result) {
        if (start == arr.length) {
            result.add(new String(arr));
            return;
        }

        for (int i = start; i < arr.length; i++) {
            if (shouldSwap(arr, start, i)) {
                swap(arr, start, i);
                permute(arr, start + 1, result);
                swap(arr, start, i); // 回溯
            }
        }
    }

    private static boolean shouldSwap(char[] arr, int start, int end) {
        for (int i = start; i < end; i++) {
            if (arr[i] == arr[end]) {
                return false;
            }
        }
        return true;
    }

    private static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
